//
// Created by xili on 2024/9/11 20:48.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int tail = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
        int cnt = (tail == 1 ? n : n - tail) / 3;
        return (int) power(3, cnt) * tail;
    }

    long long power(long long x, int n) {
        long long res = 1;
        while (n) {
            res *= n & 1 ? x : 1;
            x *= x;
            n >>= 1;
        }
        return res;
    }
};